The present invention relates to computer graphics. More specifically, the present invention relates to volume rendering using 3-D texturing units.
Surface-oriented graphics and volume graphics are two important fields within computer graphics. They differ in the way objects are represented in the computer and the way they are displayed.
A. Surface-Oriented Graphics
In surface-oriented graphics, only the surface of a given object is stored inside the computer. For practicability, a curved surface may be approximated by a potentially large number of triangles or other polygons. The triangles in turn are defined by the properties of their vertices. Thus, objects are defined by a structured list of vertices, wherein each of the vertices in turn is defined by a multitude of data items, comprising at least the geometrical coordinates. The objects, such as the body of a car and its tires, are usually defined in their own coordinate system.
A database containing all the objects is usually stored in main memory and maintained by a host CPU.
For the display, the objects are transformed into screen space according to the desired arrangement in the scene. These geometric transformations, which usually include a perspective transformation, finally give the projection of each triangle on the display area of a computer graphics output device. These transformations are usually performed by the host CPU or a specialized geometry processor.
Typically, computer graphics output devices are raster devices, i.e., the display area (or screen) comprises a set of discrete picture elements, or pixels for short. Each triangle""s projection on the screen is therefore decomposed into the set of pixels it covers, a process called scan-conversion or rasterization. Commonly, square pixels are assumed.
For each pixel inside a projected triangle, the local color of the surface is computed by applying illumination models. This process is called shading. As an example, the color of the vertices are computed prior to rasterization in accordance to location and physical behavior of the light sources in the scene. To determine an individual pixel color, the values at the vertices are then interpolated at the pixel location.
For greater realism a technique called texture mapping is widely used. In the two-dimensional case, a texture is any form of discrete image, consisting of a two-dimensional array of texture elements or texels for short. As an example, a texture can be a scanned photograph, wherein a texel consists of one numerical value for each color component (RGB). Additionally, a texture can be translucent. In this case, a texel has a fourth parameter to define the local opacity, commonly denoted by xe2x80x9cxcex1xe2x80x9d.
During the design of an object (called the modeling stage), a texture is mapped on its surface by assigning texture coordinates to the vertices of the triangles.
After projecting a triangle on the screen for display, texture mapping raises the problem of determining which portions of the texture are covered by the individual pixels, and which color is assigned to a pixel accordingly. To determine the location of the pixel projection on the texture, the texture coordinates given at the vertices are interpolated at the pixel center. However, using the RGB-triple or RGBxcex1-quadruple at or nearest to these coordinates would result in strong resampling artifacts (i.e., aliasing).
For example, in a hypothetical image consisting of a sphere and a globe (i.e., oceans, continents, ice caps etc.), the globe might cover the entire screen or just a few pixels, depending on the distance from the observer. Thus, a filter operation is performed for each pixel according to the size and shape of its projection on the texture.
For hardware systems, this is most often done using bi- or tri-linear interpolation within a xe2x80x9cMipmap.xe2x80x9d A Mipmap is a collection of pre-filtered textures, each of them being denoted a level. Level 0 holds the original texture. 2xc3x972 texels in level 0 are averaged, and the resulting value is one texel in level 1. This is continued towards the top level, which in case of square textures holds exactly one entry, the mean color of the entire texture.
For bi-linear interpolation, a level is chosen with texels best matching the size of the pixel projection. The pixel color is bi-linearly interpolated from the four texels surrounding the projection of the pixel center.
For tri-linear interpolation, two adjacent levels are chosen: one level holding the texels being smaller than the pixel projection, and the other holding larger texels. In each level, a bi-linear interpolation is performed. Finally, the two results are linearly interpolated according to the size of the pixel projection.
A typical embodiment of this method would therefore incorporate a memory system holding the Mipmap and a processor for interpolating texture coordinates across the screen triangle, accessing the texture memory and performing the interpolations.
Rasterization and the texturing are typically carried out by a combined rasterizer/texturing unit, connected to a local memory system which stores the textures.
Interpolation of the different quantities (i.e., color components RGB, texture coordinates) across a screen triangle is done by computing these values at a given vertex, hereinafter called the xe2x80x9cstarting vertex,xe2x80x9d computing the derivatives of these quantities with respect to the screen coordinates and adding the derivatives, stepping from one pixel to the next or from one line to he next.
Computing the derivatives is part of the setup stage and usually carried out by the host CPU or a dedicated setup processor.
Recently extensions to three-dimensional textures have been introduced. A 3D-texture is simply a three-dimensional array of texels. A Mipmap in this case is a collection of pre-filtered 3D-textures. An entry in level n+1 is computed from 2xc3x972xc3x972 entries in level n. For each pixel, three texture coordinates are interpolated. In the case of filtering in only one Mipmap level, a tri-linear interpolation is performed. Using two levels, two tri-linear interpolations are followed by a final linear interpolation as explained above.
3D-texture mapping has advantages whenever a 2D-texture cannot be mapped consistently on a 3D-surface, as is the case for complex-shaped wooden objects. Hardware accelerators for 3D-texture mapping are available today.
B. Volume Graphics
Volume graphics, as opposed to surface-oriented graphics, is used whenever the interior of objects is important or when there is no clearly defined surface. Typical applications include medical diagnosis, non-destructive material testing and geology.
For processing within a computer, the properties of interest (e.g., the density or the temperature) of the objects are sampled on a three-dimensional grid to give a discrete scalar field, the so-called xe2x80x9cvolume data set.xe2x80x9d The elements of a volume data set are called voxels. Usually the grid is rectangular and isotropic in at least two dimensions. Typical dimensions are 1283 up to 10243.
The visualization of these data sets consists of two parts: the segmentation, or classification, during which it is determined which subset of the data set should be visible (e.g., only the bones in a medical data set), and the meaningful display of these structures on the output device.
It may be assumed that the result of the classification is a parameter per voxel defining its visibility or opacity, hereinafter called xe2x80x9cxcex1xe2x80x9d. Usually a runs from 0 to 1, where xcex1=0 means that the voxel is completely transparent, and xcex1=1 defines a completely opaque voxel.
Furthermore it is assumed that a shading operation is performed per voxel. Each voxel is assumed to be part of a surface element, oriented according to the local gradient, and thus, illumination models from surface-oriented graphics can be applied. After classification and shading, the voxels of the data set are defined by RGBxcex1-quadruples.
For the display, or rendering, a number of methods have been developed. The most popular algorithm is raycasting. For raycasting, a camera model is constructed by defining a center of projection (the eye point) and a virtual screen, consisting of a number of pixels.
Starting from the eye point, a viewing ray is shot through the volume for each pixel on the virtual screen. Each ray is a sequence of equidistant, discrete points in-between the entry and exit points of the volume. Since the raypoints generally do not coincide with the grid points, the data set is resampled at the raypoints using a set of surrounding voxels. Most often, a tri-linear interpolation using the eight surrounding voxels is used. In the case of RGBxcex1-data sets, the four components are interpolated separately.
The color components of a raypoint are weighted by its translucency. Finally, the weighted colors of all raypoints are blended component-wise either in front-to-back or back-to-front order to give the final pixel color. This process is called compositing, which involves the application of a usually simplified absorption model according to the translucency of the individual raypoints.
C. Hardware for Volume Rendering
As of today, the number of commercially available hardware accelerators for volume rendering is much smaller than that of surface-oriented graphics accelerators.
However, RGBxcex1-volume data sets are practically identical to commonly used 3D-textures (provided they also have an opacity component). Moreover, the processing of a pixel to be textured using a 3D-texture is very similar to the processing of a raypoint. Therefore, 3D-texturing units are increasingly being used for volume rendering. For this purpose, however, the volume rendering algorithm is rearranged.
First, it is assumed that all raypoints lie on a set of equidistant planes parallel to the view plane (virtual screen). The distance of one plane to another is given by the distance of the raypoints on the ray closest to the center of the virtual screen. For perspective projections this means that the raypoint distance increases towards the edges of the virtual screen.
Instead of processing the volume data set ray by ray, processing is performed plane by plane. The plane to be processed is cut with the volume data set and the area inside the data set is decomposed into triangles. Each triangle is then rasterized to produces pixels having centers that coincide with raypoints. Each pixel is textured using the volume data set as 3D-texture.
The compositing is done with the help of a frame buffer, which is part of most graphics systems. As soon as a plane pixel is textured, the entry in the frame buffer corresponding to the associated ray is read out, and the retrieved value is blended with the newly generated one. The result is written back into the frame buffer at the same location.
Prior to rendering a given scene, the frame buffer is initialized properly to achieve correct results.
The method is functionally equivalent to raycasting, and can readily be used with 3D-texturing units if the blending (compositing) operation is supported by the 3D-texturing system. In terms of performance it is advantageous if the data set fits entirely into the texture memory. Otherwise the data set is split into sub-volumes, which are rendered sequentially.
A significant drawback of existing systems is the limited achievable performance. For each raypoint one read and one write operation is performed with the frame buffer for the compositing operation. Assuming that the number of raypoints is approximately equal to the number of voxels, and each read or write cycle takes 50 ns (optimistically), the rendering of a volume data set of 2563 voxels would take 1.68 s no matter how fast all other components are processed.
Another drawback of existing systems is that they usually cannot take advantage of large opaque structures in the data set for early ray termination, and large empty regions in the data set for empty space skipping. For most data sets, early ray termination and empty space skipping provide a substantial speed-up. Early ray termination means that the processing of a ray is terminated prior to volume exit whenever it has traversed so much (partially) opaque material that all further raypoints are hidden. Early ray termination is employed when front-to-back compositing is used. Empty space in volume data sets mostly occurs between the physical boundaries of the object (e.g., a human head) and the rectangular bounding volume of the data set.
In conclusion, it is desirable to use hardware such as 3D-textuing units for volume rendering. The 3D-texturing units are commercially available and easy to implement.
However, it would be desirable to modify the 3D-texturing units to increase rendering speed. For example, it would desirable to reduce the number of read and write operations on data in the external frame buffer. This is a serious source of inefficiency in traditional systems. Reducing the number of operations on the external frame buffer would increase rendering speed.
It would also be desirable to modify the 3D-texturing units to take advantage of early ray termination and empty space skipping. Less time would be spent on processing raypoints that do not contribute to the rendered image. Thus, taking advantage of early ray termination and empty space skipping would further reduce processing time and further increase rendering speed.
Finally, it would be desirable to increase the rendering speed while making as few modifications as possible to the 3-D texturing units.
Rendering speed is increased by the present invention. According to one aspect of the invention, an image from a volume data set is generated by dividing the image into a plurality of sub-regions, each sub-region including a plurality of pixels; and processing each sub-region one at a time. Each sub-region is processed by creating a projection of the sub-region on at least one plane cutting the volume data set, texture mapping at least one projection of the sub-region using the volume data set as texture, starting at a first plane and working towards a last plane, and compositing each textured projection after texture mapping. The composited projections are displayed.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the present invention.